package cn.qyd.kaoshi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Stream;

/**
 * @author 邱运铎
 * HJ28 素数伴侣
 * @date 2024-03-23 17:09
 */
public class PrimeNumber {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            Integer[] numbers = new Integer[n];
            for (int i = 0; i < n; i++) {
                numbers[i] = in.nextInt();
            }
            int count = 0;
            ArrayList<Integer> odds = new ArrayList<>();
            ArrayList<Integer> evens = new ArrayList<>();
            //将数组中的奇数和偶数分别存入odds和evens中
            Stream.of(numbers).forEach(num -> {
                if ((num & 1) == 1) {
                    odds.add(num);
                } else {
                    evens.add(num);
                }
            });
            //存储偶数集合中每个偶数对应的伴侣，，下标为偶数在集合中的位置，值为匹配的伴侣奇数，若没有伴侣则为初始值0
            int[] evenMatch = new int[evens.size()];
            //遍历奇数集合，将每个奇数放到偶数集合中匹配伴侣
            for (int i = 0; i < odds.size(); i++) {
                //存储当前奇数已经匹配过的偶数，下标为偶数在集合位置，值为true已经匹配过，false表示未匹配，这是为了在后面递归时不会重复去匹配，导致死循环
                boolean[] eventIsMatched = new boolean[evens.size()];
                if (findMatch(odds.get(i),evens, evenMatch,eventIsMatched)) {
                    //找到伴侣，对数+1
                    count++;
                }
            }
            System.out.println(count);
        }
    }

    public static boolean findMatch(int odd, List<Integer> evens, int[] eventMatched, boolean[] eventIsMatch) {
        //遍历偶数集合，尝试去找对应奇数的伴侣
        for (int i = 0; i < evens.size(); i++) {
            //当前偶数是否已经和该奇数匹配过，是的话跳过
            if (!eventIsMatch[i]) {
                //特别注意，这里访问过后必须立马更新值，如果放在下面if语句中，在递归中会出现死循环导致堆栈溢出
//                eventIsMatch[i] = true;
                //判断当前偶数和奇数之和是否为素数
                if (isPrime(evens.get(i) + odd)) {
                    eventIsMatch[i] = true;
                    //找到可以和该奇数组成伴侣的偶数，判断当前偶数是否已经存在伴侣，不存在直接配对，若存在尝试让当前偶数的伴侣奇数重新寻找伴侣。递归过程
                    if ( eventMatched[i] == 0 || findMatch(eventMatched[i],evens,eventMatched,eventIsMatch)) {
                        eventMatched[i] = odd;
                        return true;
                    }
                }
            }
        }
        return false;
    }

    //判断是否是素数
    public static boolean isPrime(int num) {
        if (num == 1) return false;
        for (int i = 2; i <= (int)Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}
